#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if (startGene == endGene) return 0;
        map<string, bool> hash;
        for (auto& e : bank) hash[e] = true;

        if (hash[endGene] == false) return -1;

        queue<string> q;
        q.push(startGene);

        int ret = 0, len = startGene.size();

        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string cur = q.front(); q.pop();
                for (int i = 0; i < len; i++)
                {
                    string tmp = cur;
                    static char ch[4] = { 'A','T','C','G' };
                    for (int j = 0; j < 4; j++)
                    {
                        tmp[i] = ch[j];
                        if (hash[tmp])
                        {
                            if (tmp == endGene) return ret;
                            hash[tmp] = false;
                            q.push(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};